Electronic and micromechanical devices are formed by patterning successive layers on a substrate using lithography. The patterns are formed by applying a layer of photoresist to a surface. Light is then passed through a patterned imaging plate, such as a mask or reticle, to expose the photoresist in patterns that correspond to the desired features on the substrate. A developer is applied and the photoresist is etched away leaving only the features in a pattern corresponding to the pattern on the mask. As the size of the features, such as parts of transistors, decreases, there are more features on the same size mask and the mask designs becomes more complex.
For very small features, phase shift technology (referred to as phase shift masks) is used. In a conventional non-phase shift mask, the light transmitted through adjacent transparent areas of the mask is in phase and the features are large enough that the phase of the light does not significantly affect the amount of light that hits the photoresist. Each transparent area on the mask results in a corresponding exposed area on the photoresist. With very small features, that is when the dimensions of the features are close to the wavelength of the light, diffraction occurs as the light passes through the mask. The light passing through adjacent transparent areas will interfere constructively or destructively, so that in some places on the photoresist the amplitude of the light adds together and on some places of the photoresist that light will cancel itself out.
Pitch doubling is a double patterning technique where the target layout is partitioned into two masks. The masks are used one at a time to expose the photoresist in two steps. Together the two masks reproduce the design intent. Using two masks allows features that are too close together to be produced by a single mask to be produced each by a different mask. As a result, still smaller features may be produced.
For simple grating patterns, the problem of synthesizing two masks from a target pattern can be seen as a 2-color graph coloring problem where the graph nodes are the target polygons and edges represent polygon adjacency.
However, for random polygon layouts the 2-graph coloring method quickly runs into coloring conflicts that require partitioning the polygons to mitigate the conflicts. The partitioning is then difficult to predict and to calculate. Poor partitioning can impact manufacturing yield and reduce parts quality. One reason is that when polygons are split errors can be caused by features that both masks produce. The exposure from one mask may not perfectly overlay the exposure from the next mask. This can be overcome using stringent design rules that guarantee no conflicts in the formulation of the masks and the splitting of features. However, strict rules reduce the design space and cause a loss of flexibility in design.